package se.study.binaryheap;

import java.util.Arrays;

/**
 * @Author tiger
 * @Description 二叉堆实现学习，利用最小二叉堆实现二叉堆元素操作
 * 1.二叉堆虽然是一颗完全二叉树，但它的存储方式并不是链式存储，而是顺序存储。换句话说，二叉堆的所有节点都存储在数组当中。
 * 2.假设父节点的下标是parent，那么它的左孩子下标就是 2*parent+1；它的右孩子下标就是  2*parent+2
 * @Date 11:13 2018/9/10
 */
public class HeapOperator {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 2, 6, 5, 7, 8, 9, 10, 0};
//        upAdjust(arr);
//        System.out.println("结果：" + Arrays.toString(arr));
//        System.out.println("=============================");

        buildHeap(arr);
        System.out.println("结果：" + Arrays.toString(arr));

    }

    /**
     * 构建二叉堆数据结构
     */
    public static void buildHeap(int[] arr) {
        System.out.println("原始：" + Arrays.toString(arr));
        // 从最后一个非叶子节点开始，依次下沉调整
        for (int i = (arr.length - 2) / 2; i >= 0; i--) {
            downAdjust(arr, i, arr.length);
        }
    }

    /**
     * 最后叶子节点上浮调整
     */
    public static void upAdjust(int[] arr) {
        System.out.println("原始：" + Arrays.toString(arr));
        int childIndex = arr.length - 1;
        int parentIndex = (childIndex - 1) / 2;

        // 临时存放子节点的值
        int temp = arr[childIndex];
        while (childIndex > 0 && temp < arr[parentIndex]) {
            // 如果子节点小于父节点，则子节点需上浮
            arr[childIndex] = arr[parentIndex];
            childIndex = parentIndex;
            parentIndex = (childIndex - 1) / 2;
            System.out.println("上浮：" + Arrays.toString(arr));
        }
        arr[childIndex] = temp;
    }

    /**
     * 下沉调整
     *
     * @param parentIndex 待下沉的父节点索引
     * @param length      二叉堆有效长度
     */
    public static void downAdjust(int[] arr, int parentIndex, int length) {
        System.out.println("下沉父节点：" + parentIndex);
        int minChildIndex = 2 * parentIndex + 1;
        int temp = arr[parentIndex];

        while (minChildIndex < length) {
            // 如果有右子节点，且右子节点小于左子节点，则定位到右节点
            if (minChildIndex + 1 < length && arr[minChildIndex + 1] < arr[minChildIndex]) {
                minChildIndex++;
            }

            // 如果父节点比子左右节点都小，直接跳出
            if (temp <= arr[minChildIndex]) {
                break;
            }

            // 开始交换
            arr[parentIndex] = arr[minChildIndex];
            parentIndex = minChildIndex;
            minChildIndex = 2 * parentIndex + 1;

        }
        arr[parentIndex] = temp;
        System.out.println("下沉后：" + Arrays.toString(arr));
    }
}
